// 请设计一个数据结构：LRU缓存。

class LRUCache {
    // 声明内部容量、缓存哈希表
    private readonly capacity: number;
    private cache: Map<number, number>;
    // 构造函数
    constructor(capacity: number) {
        this.capacity = capacity;
        this.cache = new Map();
    }
    // get方法
    public get(key: number) {
        // 如果哈希表中存在该键，那就先删除该键，并把它挪到最新位置
        if (this.cache.has(key)) {
            let value = (this.cache.get(key) as number);
            this.cache.delete(key);
            this.cache.set(key, value);
            return value;
        } else {
            return -1;
        }
    }
    // put方法
    public put(key: number, value: number) {
        // 容易遗漏！！需要先判断哈希表中是否存在该键，如果存在那就先删除
        if (this.cache.has(key)) {
            this.cache.delete(key);
            // 再判断内部容量是否已满，先删除哈希表最老没使用过的key
        } else if (this.capacity <= this.cache.size) {
            let oldestKey = this.cache.keys().next().value;
            this.cache.delete(oldestKey);
        }
        // 最后的操作，为哈希表添加新的数据
        this.cache.set(key, value);
    }
}

// 这道题目的数据结构设计其实也很经典了
// LRU缓存在生活中很多方面都能见到...例如说浏览器缓存、微信缓存等等
// 它的核心机制是在缓存满的时候，删除缓存里最久未使用的数据，然后再放入新元素
// 其次数据的访问时间很重要，访问时间距离现在最近，就最不容易被删除
// 首先存取数据时间性能最好的就是哈希表，因此底层的数据结构会是一个哈希表
// 剩下的操作无非是对哈希表进行一些逻辑的判断，我们要记得把get方法操作过的数据提到哈希表的最前
// 还要注意一下put方法要考虑哈希表中已存在key的情况，这是一个坑，不要删多元素了
// 此外这道题的推荐解法，可以实现插入与删除的O1时间复杂度，它的原理是在哈希表的基础上添加一条双向链表
// 思路是访问某个数据，还有删除末尾结点的需求，这样的数据结构得在头尾访问数据最快，那么这种数据结构是「双向链表」
// 双向链表的尾部存储较新访问的结点，头部是当前频次最旧的结点。双向链表在结构上是对称的，编码的时候注意保持语义一致
// 至于联立的话也很简单，我们用双向链表的节点存储哈希表的key即可
